1. Field of the Invention
This invention relates to the field of computer systems and, more particularly, to systems and methods of optimizing lock operations within computer systems.
2. Description of the Related Art
Computer systems can suffer severe performance degradation as a result of lock operations. In general, lock operations are associated with software locks which are used by computer systems to ensure that only one process at a time can access a resource, such as a critical region of memory. Throughout this specification, a memory region is used as an example of a resource associated with a lock. It is noted that the disclosed invention is equally applicable to other resources, such as an input/output location. A variety of locks have been implemented, ranging from simple spin-locks to advanced queue-based locks. Although simple spin-lock implementations can create very bursty traffic as described below, they are still the most commonly used software lock within computer systems.
Systems employing locks typically require that a given process perform an atomic operation to obtain access to a critical memory region. For example, an atomic test-and-set operation is commonly used. Generally speaking, an atomic operation is an indivisible operation. In other words, another process cannot access the lock between the test and set portion of the atomic operation. The test-and-set operation is performed to determine whether a lock bit associated withthe memory region is cleared and to atomically set the lock bit. That is, the test allows the process to determine whether the memory region is free of a lock by another process, and the set operation allows the process to acquire the lock if the lock bit is cleared.
Referring now to FIG. 1, a diagram illustrating a spin-lock implementation is shown. In a spin-lock implementation, if the test of the lock bit indicates that the memory region is currently locked, i.e. another process has acquired the lock, the requesters for the lock initiate a loop wherein the lock bit is continuously read until the lock bit is cleared, at which time the process reinitiates the atomic test-and-set operation.
Generally speaking, requesters are processes or other entities that seek to acquire the lock. Spin-locks may be implemented using either optimistic or pessimistic spin-lock algorithms. An optimistic spin-lock is depicted by the following algorithm:
______________________________________ top: atomic.sub.-- test&set ;read-to-own transaction if failed begin while busy spin ;spin on read-to-share transaction goto top end ______________________________________
For the optimistic spin-lock algorithm shown above, the process first performs an atomic test-and-set operation upon the lock bit corresponding to the memory region for which access is sought. If the atomic test-and-set operation fails, the process reads the lock bit in a repetitive fashion until the lock bit is cleared by another process. The process then reinitiates the atomic test-and-set operation. Generally speaking, a read-to-own (RTO) transactions requests write access to data and a read-to-share (RTS) transaction requests read access to data. It is noted that names other than RTO and RTS may be used to describe the concepts of acquiring read and write access to data.
A pessimistic spin-lock is depicted by the following algorithm:
______________________________________ top: while busy spin ; spin on read-to-share atomic.sub.-- test&set ; read-to-own if failed begin goto top end ______________________________________
For the pessimistic spin-lock algorithm, the process first reads the lock bit corresponding to the memory region for which access is sought in a repetitive fashion until the lock bit is cleared. When the process determines that the lock bit is clear in accordance with the read operation(s), the process performs an atomic test-and-set operation to lock and gain access to the memory region. If the test failed upon execution of the atomic test-and-set operation, the process again repetitively reads the lock bit until it is cleared.
In a shared memory computer system in which the requester performs a system bus, or global, transaction to test and set the lock, the above spin-lock algorithms create a large number of bus transactions. If the lock is not available, each requester attempting to acquire the lock bit continually performs global transactions until the lock becomes available. This large number of global transactions may adversely affect the performance of the computer system by using a large portion of the available bandwidth.
To reduce the number of global transactions performed by a spin-lock algorithm, the lock bit may be cached by each requester attempting to acquire it. In this manner, the repetitive reads to determine the state of the lock bit may be local transactions rather global transactions. While this may reduce the number of global transactions, the coherency traffic on the bus generated when the state of the lock bit changes may be unacceptable.
In a cached shared memory system, the read (or test) of the lock bit is treated as a read-to-share (RTS) operation. Since the atomic test-and-set operation includes a write, it is treated as a read-to-own (RTO) operation. The system will thus place the coherency unit containing the lock bit in a modified state in response to the atomic test-and-set operation.
For both the pessimistic and optimistic algorithms discussed above, when a memory region corresponding to a contended spin-lock is released, the owner writes to the lock to free it generating a RTO operation (1 bus transaction) which invalidates the line in the caches of all other devices. Therefore, all N spinning requesters subsequently miss and generate RTS transactions for the cache line containing the lock. The first requester to receive a data reply detects the free lock and generates an RTO transaction (1 bus transaction). Since the requester of each of the remaining RTS requests similarly receive an indication that the lock is free, each of these requesters also generates a RTO transaction (N-1 bus transactions). When the first RTO transaction is received, the requester issuing that transaction locks and gains access to the memory region. The test-and-set operations corresponding to the RTO requests of the remaining requesters therefore fail. The remaining N-2 requesters generate RTS transactions to cache the new lock bit (N-2 bus transactions).
Thus, the total number of transactions is potentially 3N-1 for the single transfer of a spin-lock from one requester to another (where N is the number of contenders for the lock). Due to this large number of transactions, the latency associated with the release of a lock until the next contender can acquire the lock is relatively high. The large number of transactions can further limit the maximum frequency at which ownership of the lock can migrate from node to node. Finally, since only one of the spinning requesters will achieve the lock, the failed test-and-set operations of the remaining processors result in undesirable RTO requests on the network. The coherency unit in which the lock is stored undesirably migrates from requester to requester, invalidating other copies. Network traffic is thereby further increased despite the fact that the lock is set.
Several lock designs to improve the performance of spin-locks have been devised, such as back-off locks and queue locks. In back-off locks, the requesters contending to acquire the lock implement a delay between attempts to acquire the lock. In this manner, the number of requesters contending for the lock at a given instance of time is reduced. The lock may be released and acquired by another requester before some requesters detect that the lock has been freed. Accordingly, the number of processes that attempt to acquire the lock when it becomes available is reduced. Low contention for the lock reduces the number of transactions when the lock changes state. The requesters that do not contend for the lock will generate a read-to-share transaction to read the new lock bit, but will not generate the read-to-share and read-to-own transactions to attempt to acquire the lock.
The delay implemented by a backup lock may be constant or variable. In a constant delay implementation, the requester delays a fixed time between attempted accesses to the lock. In a variable delay implementation, the duration of the delay may be different for different requesters. An exponential back-off lock is one example of variable delay back-off lock. In a exponential back-off lock, the delay implemented by the requester increases with each unsuccessful attempt to acquire the lock.
Back-off locks unfortunately may delay the acquisition of the lock. When a lock becomes available, a delay may occur before a process attempts to acquire the lock. This delay can increase the latency of a lock operation and reduce the performance of the computer system. Further, back-off locks can create fairness problems. Because each contending process has an equal chance of acquiring the lock, a process then has just begun waiting for the lock may be more likely to acquire the lock before a process that has been waiting for a long time. It is also theoretically possible for a waiting process to never acquire the lock.
Queue locks are another technique for reducing the overhead of lock operations. Referring now to FIG. 2, each requester for the lock is queued up behind earlier requesters. In this manner, only the process at the head the queue attempts to acquire the lock when it becomes available and generates bus transactions. Queue locks have the added benefit that they may be more fair than spin-locks because the earlier processes get the lock before processes that enter the queue later.
Unfortunately, in practice, queue locks have several disadvantages. For example, queue locks require space proportional to the number of queued requesters instead of the constant space required by spin-locks. This may make queue locks incompatible with some synchronization library interfaces. Further, if the process at the head of the queue is suspended or currently not running, the other processes behind the suspended process may not be able to acquire the lock. Still further, queue locks may be less efficient then spin locks if there is no contention for lock. Overhead may be incurred to check the queue to verify that no requesters are waiting to acquire the lock.